import { Rect } from "./Rect";

export interface treeObj<T> {
    target: T;
    rect: Rect;
}

export class QuadTree {

    //一个节点所能持有的最大对象数量，如果超过则进行分裂
    private MAX_OBJECT: number = 3;

    //子节点的最大深度
    private MAX_LEVELS = 10;

    private level: number = 0;

    private objArr: Array<treeObj<any>>;

    private rect: Rect;

    private nodes: QuadTree[];

    public constructor(pLevel: number, rect: Rect) {

        this.level = pLevel;

        this.objArr = [];

        this.rect = rect;

        this.nodes = [];
    }

    public clear() {

        this.objArr = [];

        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i]) {
                this.nodes[i].clear();
            }
        }

        this.nodes = [];
    }

    public split(): void {
        let nextLevel = this.level + 1;
        let subWidth = Math.floor(this.rect.width >> 1);
        let subHeight = Math.floor(this.rect.height >> 1);

        let offsetX = Math.floor(this.rect.x);
        let offsetY = Math.floor(this.rect.y);

        this.nodes[0] = new QuadTree(nextLevel, new Rect(offsetX + subWidth, offsetY, subWidth, subHeight));
        this.nodes[1] = new QuadTree(nextLevel, new Rect(offsetX, offsetY, subWidth, subHeight));
        this.nodes[2] = new QuadTree(nextLevel, new Rect(offsetX, offsetY + subHeight, subWidth, subHeight));
        this.nodes[3] = new QuadTree(nextLevel, new Rect(offsetX + subWidth, offsetY + subHeight, subWidth, subHeight));

    }

    private getIndex(bounds: Rect): number[] {

        var indexes: number[] = [];

        let verticalMidpoint = this.rect.x + (this.rect.width >> 1);
        let horizontalMidpoint = this.rect.y + (this.rect.height >> 1);

        var startIsNorth = bounds.y < horizontalMidpoint,
            startIsWest = bounds.x < verticalMidpoint,
            endIsEast = bounds.x + bounds.width > verticalMidpoint,
            endIsSouth = bounds.y + bounds.height > horizontalMidpoint;

        //top-right quad
        if (startIsNorth && endIsEast) {
            indexes.push(0);
        }

        //top-left quad
        if (startIsWest && startIsNorth) {
            indexes.push(1);
        }

        //bottom-left quad
        if (startIsWest && endIsSouth) {
            indexes.push(2);
        }

        //bottom-right quad
        if (endIsEast && endIsSouth) {
            indexes.push(3);
        }

        return indexes;

    }

    public insert<T>(obj: treeObj<T> | treeObj<T>[]): void {

        if (obj instanceof (Array)) {
            for (let i in obj) {
                this.insert(obj[i]);
            }
            return;
        }

        if (this.nodes.length) {
            var indexes = this.getIndex(obj.rect);
            for (let i = 0; i < indexes.length; i++) {
                this.nodes[indexes[i]].insert(obj);
            }
            return;
        }

        this.objArr.push(obj);

        if (this.objArr.length > this.MAX_OBJECT && this.level < this.MAX_LEVELS) {
            if (!this.nodes.length) {
                this.split();
            }

            for (let i = 0; i < this.objArr.length; i++) {
                indexes = this.getIndex(this.objArr[i].rect);
                for (var k = 0; k < indexes.length; k++) {
                    this.nodes[indexes[k]].insert(this.objArr[i]);
                }
            }

            //clean up this node
            this.objArr = [];
        }

    }

    public getAllObjects(): any[] {
        let arr = [];

        for (let i = 0; i < this.nodes.length; i++) {
            arr = arr.concat(this.nodes[i].getAllObjects());
        }

        for (let i = 0; i < this.objArr.length; i++) {
            arr.push(this.objArr[i]);
        }

        return arr;
    }

    // Return all objects that the object could collide with
    public findObjects<T>(bounds: Rect): Array<treeObj<T>> {
        let returnObjects = this.objArr;

        if (this.nodes.length) {
            var indexes = this.getIndex(bounds);
            for (var i = 0; i < indexes.length; i++) {
                returnObjects = returnObjects.concat(this.nodes[indexes[i]].findObjects(bounds));
            }
        }

        //remove duplicates
        returnObjects = returnObjects.filter(function (item, index) {
            return returnObjects.indexOf(item) >= index;
        });

        return returnObjects;
    }
}

